package com.easy.leetcode.bit;

import java.util.HashMap;
import java.util.Map;

/**
 * 137. 只出现一次的数字 II
 *
 * 给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。请你找出并返回那个只出现了一次的元素
 */
public class SingleNumber137 {
    public int singleNumber(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for (int num : nums) {
           map.put(num,map.getOrDefault(num,0)+1) ;
        }
        for (int num : nums) {
            if (map.get(num)==1){
                return num;
            }
        }
        return -1;
    }

    /**
     * 右移 ：高位补0
     * 长度32数组，用来记录每一位上出现1出现的次数，
     * 每一位上的个数对3取余，不为0 的是要求的数，
     * 对应位置上的值左移i 位，叠加得到的值就是要求的数
     *
     * @param nums
     * @return
     */
    public int singleNumber1(int[] nums) {
        int[] arr = new int[32];
        int res=0;
        for (int num : nums) {
            for (int i = 0; i < 32; i++) {
                if(((num>>i)&1)==1){
                    arr[i]++;
                }
            }
        }
        for (int i = 0; i < 32; i++) {
            if (arr[i]%3!=0){
              res=res+ (1<<i);
            }
        }
        return res;
    }
}
